/*
Recover Binary Search Tree My Submissions Question Solution
Total Accepted: 40454 Total Submissions: 164184 Difficulty: Hard
Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?
confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.
*/

#include <iostream>
#include <vector>
#include <string>

using namespace std;


//Definition for singly-linked list.
struct ListNode {
	int val;
	ListNode *next;
	ListNode(int x) : val(x), next(NULL) {}
};



struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int x) : val(x), left(NULL), right(NULL) {}

};

class Solution {
public:
	TreeNode *pre ;
	TreeNode *p;
	TreeNode *q;
	void recoverTree(TreeNode* root) {

		pre = NULL;
		p = NULL;
		q = NULL;

		dfs(root);
		int temp = p->val;
		p->val = q->val;
		q->val = temp;

	}

	void dfs(TreeNode* root)
	{
		if (root == NULL)
		{
			return;
		}

		dfs(root->left);
		if (pre!=NULL && pre->val >root->val)
		{
			if (p == NULL)
			{
				p = pre;
				q = root;
			}
			else
			{
				q = root;
			}

		}
		pre = root;
		dfs(root->right);
	}
};


int main()
{
	cout << "The lenght of the list :  " << endl;

	/*int length;
	cout << "Input the length: " << endl;

	cin >> length;


	ListNode* head = new ListNode(-1);
	ListNode* p = new ListNode(-1);
	p = head;

	while (length--)
	{
	int item;
	cin >> item;
	ListNode* q = new ListNode(item);
	p->next = q;
	p = p->next;

	}

	head = head->next;

	cout << "Input the m, n: " << endl;
	int m = 1, n = 1;
	cin >> m >> n;*/

	string str = "25525511135";
	//Solution s;
	//vector<string> strVec;

	//strVec = s.restoreIpAddresses(str);

	cout << "The result: " <<str[0]<< endl;

	system("pause");

	return 0;
}